对于有向图的路径存储，有很多种方法，例如邻接表，邻接矩阵等。但是他们都有各自的局限性，而链式前向星几乎是有向图存储的最优解。

1.什么是链式前向星？

链式前向星是一种静态链表存储和集边数组储存，可以快速访问一个顶点所有的指向顶点，是一种在算法竞赛中常见的存储有向图的方式。

2.存储结构

通常来说，我们会使用

head[]来存储访问的头节点所存储最后一条边的值。

使用一个结构体来存储每条边的信息。

struct Edge
{
  int to;  //to表示指向的下一个顶点
  int w; //w表示这条边的值
  int next; //next表示该边指向的下一条边的值
}edge[];

3.存储方式

通常来讲，一般使用一个函数存储。

void add(int from,int to,int w)
{
  cnt++;
  edge[cnt].next=head[from];
  edge[cnt].to=to;
  edge[cnt].w=w;
  head[from]=cnt;
}

根据这个函数可以轻易看出来，我们将edge信息存储在一个有后往前访问的链式表中，而这就是链式前向星。

4.链式前向星的访问

for(int i=head[start_point];i;i=edge[i].next)
{
 int to=edge[i].to;
 // function

 //function end
}

5.总结

链式前向星是一种高效的有向图存储方式，善用链式前向星是在算法竞赛中高效解决图的问题的基础。